1. Field of the Invention
The present invention relates to computer-implemented data modeling, and more specifically to a method and apparatus for representing data, having multi-dimensional input vectors and corresponding output element, by piece-wise polynomials.
2. Related Art
There are several instances in which data having multi-dimensional input vectors and corresponding output element is present. For example, data representing cell library characterization (used in computer aided design of integrated circuits) may contain several dimensions to each input vector (e.g., fabrication process, voltage, temperature, an output load, input transition time), and corresponding output elements (e.g., delay offered, timing constraint, leakage power, power consumed) for each cell-type in a library.
There is often a need to represent such data by a polynomial. As an illustration, in the case of cell library characterization, assuming that the data corresponding to each output element is represented in the form of a table, there could be several possible values for each dimension, thereby making the size of the table very large. For example, assuming that there are X1, X2, X3, . . . XN possible values for each of N-dimensions (in the input vectors), the total number of rows in the table would be X1*X2*X3 . . . *XN (wherein * represents the multiplication operation.)
As may be appreciated from the above computation, the total number of rows in a table (for an output element) can become large with a large number of dimensions and/or a large number of possible values for each dimension. One problem with such large number of rows in a table is that determining the output element for a specific input vector combination may require unduly high resources (e.g., a large memory to store the entire table or a large number of computations using techniques such as hashing).
Accordingly, there has been recognised a general need to model such large volumes of data with a polynomial, having a variables corresponding to the dimensions of the input vectors. The polynomial should ideally generate the same value of the output element when the corresponding specific value combination for an input vector is substituted for the variable in the polynomial. Accordingly, once the polynomial is accurately determined, the specific output element value for an input vector value combination, can be computed by using the polynomial.
Several general techniques have been attempted in the relevant arts to determine such polynomials. Once such technique is based on curve fitting, in which a curve is sought to be computed mathematically such that deviations of the computed values from the actual are within an acceptable range.
One problem with such curve fitting technique is that no curve may be present (even in theory) to fit all the data for a specific output element value. Accordingly, it has been proposed to partition the entire data set into multiple subsets, with a piece-wise polynomial being determined for each subset (with the desired degrees of accuracy). For example, it has been proposed CAD tool vendors such as Synopsis Inc. (of Mountain View Calif.) that cell library characterization data can be provided in the form of piece-wise polynomials.
What is therefore required is a method and apparatus for representing data, having multi-dimensional input vectors and corresponding output element, by piece-wise polynomials.
In the drawings, like reference numbers generally indicated identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears in indicated by the leftmost digit(s) in the corresponding reference number.